#ifndef __QUEUE__
#define __QUEUE__
/*
这个头文件中记录了一个泛型queue类的实现，底层使用链表
*/

#include<iostream>
using namespace std;

template<typename Type> class Queue;
template<typename T> 
ostream& operator<< (ostream&, const Queue<T>&);

//Queue_item所有成员全是private，不希望被外部访问，只允许通过queue类间接访问
template<typename Type>
class Queue_item{
    friend class Queue<Type>;
    friend ostream& operator<< <Type> (ostream&, const Queue<Type>&);
    Queue_item(const Type& t):item(t), next(nullptr){}

    Type item;
    Queue_item* next;
};

template<typename Type>
class Queue{
    friend ostream& operator<< <Type> (ostream&, const Queue<Type>&);

public:
    Queue(): head(nullptr), tail(nullptr){}
    template<class It>
    Queue(It beg, It end): head(nullptr), tail(nullptr){copy_elems(beg, end);}
    
    Queue(const Queue& other):head(nullptr), tail(nullptr){copy_elems(other);}
    Queue& operator=(const Queue& other){destroy(); copy_elems(other); return *this;}
    ~Queue(){destroy();}

    template<class Iter> void assign(Iter, Iter);
    Type& front(){return head->item;}
    const Type& front() const {return head->item;}
    void push(const Type&);
    void pop();
    bool empty() const {return head == nullptr;}
private:
    Queue_item<Type>* head;
    Queue_item<Type>* tail;
    void destroy();
    void copy_elems(const Queue&);
    template<class Iter>
    void copy_elems(Iter, Iter);
};

template<typename T> 
ostream& operator<< (ostream& os, const Queue<T>& q){
    os << "< ";
    Queue_item<T> *p;
    for(p = q.head; p; p = p->next)
        os << p->item << " ";
    
    os << ">" << endl;
    return os;
}

template<typename Type>
void Queue<Type>::pop(){
    if(empty())
        return;
    auto temp = head;
    head = head->next;
    delete temp;
}

template<typename Type>
void Queue<Type>::push(const Type& val){
    Queue_item<Type>* curr = new Queue_item<Type>(val);
    if(empty())
        head = tail = curr;
    else{
        tail->next = curr;
        tail = curr;
    }
}

template<typename Type>
void Queue<Type>::destroy(){
    while(!empty())
        pop();
    head = nullptr;
    tail = nullptr;
}

template<typename Type>
void Queue<Type>::copy_elems (const Queue<Type>& other){
    for(auto curr = other.head; curr; curr = curr->next)
        push(curr->item);
}

template<typename Type> template<class Iter>
void Queue<Type>::copy_elems(Iter beg, Iter end){
    while(beg != end){
        push(*beg);
        beg++;
    }
}

template<typename Type> template<class Iter>
void Queue<Type>::assign(Iter beg, Iter end){
    destroy();
    copy_elems(beg, end);
}

#endif